The China State Encryption Administration proclaimed SM2 and SM3 cryptographic algorithms in December, 2010, marking the moment that the SM2 and SM3 cryptographic algorithms enter a commercial phase. As a component of the SM2 cryptographic algorithm, the SM2 key exchange protocol is applied well in the functional fields of key administration and key negotiation. In the process of implementing SM2 key exchange protocol engineering, the parameter W is an important parameter in the key exchange protocol, and the generating operation efficiency of the parameter value becomes a decisive factor for the implementing efficiency of the whole key exchange protocol.
Based on provisions of the SM2 key exchange protocol, the existing key negotiation procedure is as follows:
It is supposed that a user A is a key negotiation initiator, a user B is a key negotiation responder, the length of key data obtained through the negotiation between the user A and the user B is klen bits, and both the user A and the user B use the same elliptic curve equation, wherein the elliptic curve equation type can be selected from a prime field equation y2=x3+ax+b or a quadratic extension field equation y2+xy=x3+ax2+b.
A key derivation function specified in the SM2 key exchange protocol is recorded as KDF(Z,klen), which is used for deriving key data from a secret bit string, wherein Z is an input secret bit string; the integer klen represents the bit length of the key data to be obtained and the value thereof is required to be smaller than (232−1)v; and the bit string of the key data having a length of klen is recorded as K. In the process of generating the key data, the key derivation function needs to call a cryptographic hash function (e.g., SM3 cryptographic hash algorithm), and generally, the cryptographic hash function is recorded as Hv( ), and the output of the cryptographic hash function is a hash value having a length of v bits.
Operation steps of the key derivation function will be introduced below:
(1) Initializing a counter composed of 32 bits ct=0x00000001;
(2) Executing the following step a and step b circularly by adopting values of i from 1 to ┌klen/v┐ respectively, wherein execution results of respective times are respectively recorded as Ha1, Ha2 . . . Ha┌klen/v┐−1 and Ha!┌klen/v┐, and Ha!┌klen/v┐ is a part or all of the value of the last generated Hai:
a, calculating Hai=Hv(Z∥ct), wherein ∥ is cascade operation;
b, Ct++;
In the process of calculating Ha!┌klen/v┐, is an integer, then let Ha!┌klen/v┐=Ha┌klen/v┐; and if klen/v is not an integer, then let Ha!┌klen/v┐ be the leftmost (klen−(v×└klen/v┘)) bits in Ha┌klen/v┐.
(3) Finally, making K=Ha1∥Ha2∥ . . . ∥Ha┌klen/v┐−1∥Ha!┌klen/v┐, wherein K is the obtained key data.
Based on the obtained key derivation function, the user A and the user B need to perform key negotiation in order to obtain the same key, and specific operation steps are as follows:
Recording w=┌(┌log2(n)┐/2┐−1.
User A:
A1: generating a random number rAε[1, n−1] by using a random number generator;
A2: calculating an elliptic curve point RA=[rA]G=(x1, y1), wherein (x1, y1) are coordinate values of the point RA, and G is a selected elliptic curve parameter.
A3: sending RA to the user B;
User B:
B1: generating a random number rBε[1, n−1] by using a random number generator;
B2: calculating an elliptic curve point RB=[rB]G=(x2, y2), wherein (x2, y2) are coordinate values of the point RB, and G is a selected elliptic curve parameter;
B3: extracting a field element x2 from RB, converting the data type of the field element x2 into an integer firstly if the field element x2 is quadratic extension field data or directly performing subsequent operations without conversion if the field element x2 is prime field data; and then calculating an intermediate parameter x2 at the user B side, wherein x2=2w+(x2&(22−1);
B4: calculating tB=(dB+ x2·rB) modn, wherein tB is an intermediate parameter at the user B side, dB is a private key stored locally by the user B, and rB is the random number generated locally by the user B;
B5: verifying whether RA satisfies an elliptic curve equation (the user B can agree with the user A by using a prime field mode or a quadratic extension field mode in advance that they both adopt the same elliptic curve equation), if not, determining that this key negotiation fails, otherwise extracting a field element x1 from RA, converting the data type of the field element x1 into an integer firstly if the field element x1 is quadratic extension field data or directly performing subsequent operations without conversion if the field element x1 is prime field data, and calculating an intermediate parameter x1 at the user B side, wherein x1=2w+(x1&(2w−1));
B6: calculating an elliptic curve point V=[h·tB](PA+[ x1]RA)=(xv, yv), wherein h is a selected elliptic curve parameter, and PA is a public key of the user A, and judging whether V is an infinite point (e.g., xV=0, YV=0), if so, confirming that the key negotiation of the user B fails, otherwise converting the data types of the field elements xV and YV into bit strings;
B7: calculating KB=KDF(xV∥yV∥ZA∥ZB, klen), wherein KB is key data obtained by the user B through the key negotiation, and at this moment, it can be confirmed that the key negotiation of the user B succeeds by default.
Optionally, after executing B7, the user B can further execute B8:
B8: converting the data types of coordinates x1 and y1 of RA and coordinates x2 and y2 of RB into bit strings, and calculating SB=Hash (0x02∥yV∥Hash(xV∥ZA∥ZB∥x1∥y1∥x2∥y2)), wherein Hash( ) can be treated as a cryptographic hash function Hv( ), and SB can be treated as a hash value obtained through the operation.
B9: sending RB to the user A, and if B8 is executed, further sending SB to the user A;
User A:
A4: extracting the field element x1 from RA, converting the data type of the field element x1 into an integer if the field element x1 is quadratic extension field data or directly performing subsequent operations without conversion if the field element x1 is prime field data, and calculating the intermediate parameter x1, wherein x1=2w+(x1&(22−1));
A5: calculating tA=(dA+ x1·rA) mod n, wherein tA is an intermediate parameter at the user A side, dA is a private key stored locally by the user A, and rA is the random number generated locally by the user A;
A6: verifying whether RB satisfies an elliptic curve equation (agreed with the user B), if not, determining that this key negotiation fails, otherwise extracting the field element x2 from RB, converting the data type of the field element x2 into an integer firstly if the field element x2 is quadratic extension field data or directly performing subsequent operations without conversion if the field element x2 is prime field data, and calculating the intermediate parameter x2, wherein x2=2w+(x2&(21−1));
A7: calculating an elliptic curve point U=[h·tA](PB+[ x2]RB)=(xU, yU), confirming that the negotiation of the user A fails if U is an infinite point (e.g., xU=0, yU=0), otherwise converting the data types of the field elements xU and yU into bit strings;
A8: calculating KA=KDF(xU∥yU∥ZA∥ZB, klen), wherein KA is key data obtained by the user A through the key negotiation, and at this moment, it can be confirmed that the key negotiation of the user A succeeds by default;
Optionally, after executing A8, the user A can further execute A9 and A10 if receiving SB sent by the user B:
A9: converting the data types of coordinates x1 and y1 of RA and coordinates x2 and y2 of RB into bit strings, and calculating S1=Hash(0x02∥yU∥Hash(xU∥ZA∥ZB∥x1∥y1∥x2∥y2)), wherein Hash( ) can be treated as a cryptographic hash function Hv( ), and S1 can be treated as a hash value obtained through the operation, and checking whether S1=SB is satisfied, if so, determining that the key confirmation from the user B to the user A succeeds, otherwise determining that the key confirmation from the user B to the user A fails;
A10: calculating SA=Hash(0x031∥yU∥Hash(xU∥ZA∥ZB∥x1∥y1∥x2∥y2)), and sending SA to the user B.
User B: (the user B can further execute steps B10 and B11 if receiving SA sent by the user A)
B10: calculating S2=Hash(0x03∥yV∥Hash(xV∥ZA∥ZB∥x1∥y1∥x2∥y2)), and checking whether S2=SA is satisfied, if so, determining that the key confirmation from the user A to the user B succeeds, otherwise determining that the key confirmation from the user A to the user B fails.
The above-mentioned process is the key negotiation process described by the SM2 key exchange protocol. It can be seen that in the above-mentioned procedure, the operational formula of the parameter value of W is w=┌(┌log2(n)┐/2)┐−1, wherein n is the elliptic curve parameter and also called Order n, and the Order n is generally a big integer containing 160 bits or above. If the logarithm value of log2(n) is directly solved based on the Order n and then round-up operation is performed, this is relatively complex during engineering implementation and consumes too much calculating time, thus directly reducing the implementation efficiency of the key negotiation procedure and increasing the implementation complexity of the key negotiation procedure.